package algorithms.a07graphBasics;

import com.google.common.base.Preconditions;
import com.google.common.collect.Sets;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * 稠密图 - 邻接矩阵
 *
 * @author 王昊然
 * @create 2018-02-24 15:12
 **/
public class DenseGraph implements Graph{

    private int n; //节点数量（同时每一个点的值也是下标）
    private int m; //边的数量
    private boolean isDirected; //true有向图 false无向图
    private boolean[][] g; //节点之间边的信息 true为有边 false无边

    public DenseGraph(int n, boolean isDirected) {
        this.n = n;
        this.m = 0;
        this.isDirected = isDirected;
        g = new boolean[n][n]; //boolean初始化即为false
    }

    public int V() {
        return n;
    }//返回节点数

    public int E() {
        return m;
    }//返回边的个数

    public void addEdge(int v, int w) {

        if(hasEdge(v, w)) return;

        g[v][w] = true;
        if (!isDirected) {
            g[w][v] = true;
        }
    }

    /**
     * 判断两点间是否有边
     * 不用考虑边是否有向无向，只判断v到w的情况
     * @param v
     * @param w
     * @date: 2018/2/24 15:33
     * @author: 王昊然
     */
    public boolean hasEdge(int v, int w) {
        Preconditions.checkArgument(v < n && w < n, "节点值超出范围");

        return g[v][w];
    }

    /**
     * 返回某一个点所有连接点的迭代器
     *
     * @param v
     * @date: 2018/2/26 9:38
     * @author: 王昊然
     */
    public Set<Integer> adj(int v){
        Preconditions.checkArgument(v < n, "节点值超出范围");

        Set<Integer> set = Sets.newHashSet();

        for (int i = 0; i < n; i++) {
            if(g[v][i]){
                set.add(i);
            }
        }
        return set;
    }

    // 显示图的信息
    public void show(){

        for( int i = 0 ; i < n ; i ++ ){
            for( int j = 0 ; j < n ; j ++ )
                System.out.print(g[i][j]+"\t");
            System.out.println();
        }
    }
}
